package 中等.贪心思想;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个字符串数组 words 。words 中每个元素都是一个包含 两个 小写英文字母的单词。
 * 请你从 words 中选择一些元素并按 任意顺序 连接它们，并得到一个 尽可能长的回文串 。每个元素 至多 只能使用一次。
 * 请你返回你能得到的最长回文串的 长度 。如果没办法得到任何一个回文串，请你返回 0 。
 * 回文串 指的是从前往后和从后往前读一样的字符串。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-palindrome-by-concatenating-two-letter-words
 */
public class 连接两字母单词得到的最长回文串_2131 {

    public static void main(String[] args) {

        System.out.println(longestPalindrome(new String[]{"qo", "ff", "qq", "qf", "of", "of", "oo", "of", "qf", "qf"}));

    }

    /**
     * 类似 ls sl 和 aa  aa 的单词都能够进行抵消，每次抵消长度 +4
     * 如果抵消完成后，还剩下两个字符相等的 xx 可以加入到回文字符串 +2
     *
     * @param words
     * @return
     */
    public static int longestPalindrome(String[] words) {
        int count = 0;
        Map<String, Integer> map = new HashMap<>();

        for (String word : words) {
            Integer wCount = map.getOrDefault(word, 0);
            if (wCount > 0) {
                map.put(word, wCount - 1);
                count += 4;
                continue;
            }
            String reverseWord = new StringBuilder(word).reverse().toString();
            map.put(reverseWord, map.getOrDefault(reverseWord, 0) + 1);
        }

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() > 0) {
                String word = entry.getKey();
                if (word.charAt(0) == word.charAt(1)) {
                    return count + 2;
                }
            }
        }
        return count;
    }

}
